package j2024.j202408;

import java.util.Arrays;

public class j0813 {
    /**
     * 62. 不同路径
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m+1][n+1];
        dp[0][1] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m][n];
    }

    /**
     * 179. 最大数
     * @param nums
     * @return
     */
    public String largestNumber(int[] nums) {
        int n = nums.length;
        String[] strs = new String[n];
        for (int i = 0; i < n; i++) {
            strs[i] = ""+nums[i];
        }
        Arrays.sort(strs,(a,b)->{
            return (b+a).compareTo(a+b);
        });
        StringBuilder ret = new StringBuilder();
        for(String s: strs){
            ret.append(s);
        }
        if(ret.charAt(0)=='0'){
            return "0";
        }
        return ret.toString();
    }


    /**
     * 63. 不同路径 II
     * @param obstacleGrid
     * @return
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length,n = obstacleGrid[0].length;
        int[][] dp = new int[m+1][n+1];
        dp[0][1] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if(obstacleGrid[i-1][j-1]==1){
                    dp[i][j] = 0;
                }else {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        return dp[m][n];
    }


    /**
     * LCR 166. 珠宝的最高价值
     * @param frame
     * @return
     */
    public int jewelleryValue(int[][] frame) {
        int m = frame.length;
        int n = frame[0].length;
        int[][] dp = new int[m+1][n+1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = frame[i-1][j-1] + Math.max(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[m][n];
    }


    /**
     * 931. 下降路径最小和
     * @param matrix
     * @return
     */
    public int minFallingPathSum(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m+1][n+2];
        for (int i = 1; i < m+1; i++) {
            for (int j = 0; j < n+2; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Math.min(Math.min(dp[i-1][j-1],dp[i-1][j]),dp[i-1][j+1])+matrix[i-1][j-1];
            }
        }
        int ret = Integer.MAX_VALUE;
        for (int i =  1; i <= n; i++) {
            ret = Math.min(ret,dp[m][i]);
        }
        return ret;
    }


    /**
     * 64. 最小路径和
     * @param grid
     * @return
     */
    public int minPathSum(int[][] grid) {
        int  m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m+1][n+1];
        for (int i = 0; i < m+1; i++) {
            dp[i][0] = Integer.MAX_VALUE;
        }
        for (int i = 0; i < n+1; i++) {
            dp[0][i] = Integer.MAX_VALUE;
        }
        dp[0][1] = 0;dp[1][0] = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = grid[i-1][j-1]+Math.min(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[m][n];
    }


    /**
     * 174. 地下城游戏
     * @param dungeon
     * @return
     */
    public int calculateMinimumHP(int[][] dungeon) {
        int m =dungeon.length;
        int n = dungeon[0].length;
        int[][] dp = new int[m+1][n+1];
        for (int i = 0; i <= m; i++) {
            dp[i][n] = Integer.MAX_VALUE;
        }
        for (int i = 0; i <= n; i++) {
            dp[m][i] = Integer.MAX_VALUE;
        }
        dp[m][n-1] = 1;dp[m-1][n] = 1;
        for (int i = m-1; i >=0 ; i--) {
            for (int j = n-1; j >=0 ; j--) {
                dp[i][j] =  Math.min(dp[i+1][j],dp[i][j+1])-dungeon[i][j];
                dp[i][j] = Math.max(dp[i][j],1);
            }
        }
        return dp[0][0];
    }
}
